/*********************************************************
   Copyright: (C) 2008-2010 by Steven Schveighoffer.
              All rights reserved

   License: Boost Software License version 1.0

   Permission is hereby granted, free of charge, to any person or organization
   obtaining a copy of the software and accompanying documentation covered by
   this license (the "Software") to use, reproduce, display, distribute,
   execute, and transmit the Software, and to prepare derivative works of the
   Software, and to permit third-parties to whom the Software is furnished to
   do so, all subject to the following:

   The copyright notices in the Software and this entire statement, including
   the above license grant, this restriction and the following disclaimer, must
   be included in all copies of the Software, in whole or in part, and all
   derivative works of the Software, unless such copies or derivative works are
   solely in the form of machine-executable object code generated by a source
   language processor.

   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
   SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
   FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
   DEALINGS IN THE SOFTWARE.

**********************************************************/
module dcollections.model.Multiset;

public import dcollections.model.Addable;

/**
 * A Multiset is a container that allows multiple instances of the same value
 * to be added.
 *
 * It is similar to a list, except there is no requirement for ordering.  That
 * is, elements may not be stored in the order added.
 *
 * Since ordering is not important, the collection can reorder elements on
 * removal or addition to optimize the operations.  Indeed most of the
 * operations guarantee better performance than an equivalent list operation
 * would.
 */
interface Multiset(V) : Addable!V, Iterator!V, Purgeable!V
{
    /**
     * clear all elements from the multiset (part of collection
     * pseudo-interface)
     */
    Multiset clear();

    /**
     * dup (part of collection pseudo-interface)
     */
    Multiset dup();

    /**
     * Remove an element from the multiset.  Guaranteed to be O(lgN) or better.
     */
    Multiset remove(V v);

    /**
     * Covariant add (from Addable)
     */
    Multiset add(V[] elems...);

    /**
     * Covariant add (from Addable)
     */
    Multiset add(Iterator!(V) it);

    /**
     * remove all elements with the given value from the multiset.  Guaranteed
     * to be O(lgN*M) or better, where N is the number of elements in the
     * multiset and M is the number of elements to be removed.
     */
    Multiset removeAll(V v);

    /**
     * gets the most convenient element in the multiset.  Note that no
     * particular order of elements is assumed, so this might be the last
     * element added, might be the first, might be one in the middle.  This
     * element would be the first iterated if the multiset is used as an
     * iterator.  This will be faster than finding a specific element because
     * it's guaranteed to be O(1), where finding a specific element is only
     * guaranteed to be O(lgN).
     */
    @property inout(V) get() inout;

    /**
     * Remove the most convenient element in the multiset and return its
     * value.  This is equivalent to (v = get(), remove(v), v), but only
     * does one lookup.
     */
    V take();

    /**
     * Count all the instances of v in the multiset.  Guaranteed to run in
     * O(lgn * m) or better, where n is the number of elements in the multiset,
     * and m is the number of v elements in the multiset.
     */
    size_t count(const(V) v) const;
}
